package com.zxy.javaarithmetic.chapter_1_StackQueue;

import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_1_StackQueue
 *  @文件名:   P_1_getMinStack
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/3 10:37
 *  @描述：    设计可获取栈中最小值的栈，pop,push,getMin 时间复杂度为O(1)
 */
public class P_1_getMinStack {

	public static void main(String[] args) {
		MyStack stack = new MyStack();

		for (int i = 0; i < 10; i++) {
			stack.push((int) (1 + Math.random() * 100));
		}
		System.out.println(stack);

		for (int i = 0; i < 10; i++) {
			System.out.println(stack + "  最小值=" + stack.getMin());
			stack.pop();
		}
	}

	public static class MyStack {

		private Stack<Integer> mStack;
		private Stack<Integer> minStack;

		public MyStack() {
			mStack = new Stack<>();
			minStack = new Stack<>();
		}

		public void push(Integer element) {
			mStack.push(element);
			if (minStack.isEmpty()) {
				minStack.push(element);
			} else {
				if (element <= minStack.peek()) {
					minStack.push(element);
				}
			}
		}

		public Integer pop() {
			if (mStack.isEmpty()) {
				throw new RuntimeException("your stack isEmpty");
			}
			Integer element = mStack.pop();
			if (!minStack.isEmpty() && getMin() == element) {
				minStack.pop();
			}
			return element;
		}

		public Integer getMin() {
			if (minStack.isEmpty()) {
				throw new RuntimeException("your stack isEmpty");
			}
			return minStack.peek();
		}

		@Override
		public String toString() {
			return mStack.toString();
		}
	}
}
